CF1139D Steps to One 解题报告

Description

给一个数列,每次随机从 [1,m][1,m] 中选择一个数添加到数列末尾,直至数列的 gcd=1\gcd =1 时停止。求期望长度。
1m1051\leq m\leq 10^5

Solution

阅读全文 »

ARC101E Ribbons on Tree 解题报告

Description

给定一棵大小为 nn 的树,你需要给树上的点两两配对,对于一组对子 (u,v)(u,v) ,在树上将 uvu\rightarrow v 的路径染色。定义一个配对方案合法当且仅当所有边都有颜色。
求方案数对 109+710^9 + 7 取模。
n5×103,2nn\leq 5\times 10^3,2|n

阅读全文 »

树形 DP 泛做

博主鉴于自己的树形 dp 水平太 low 前段时间专门练习了下树形 dp。
就把题解和方法整理在一篇博客里算了。
希望自己以后遇到树形 dp 的题目能有更多准确的想法吧 🌹。


阅读全文 »

[ZJOI2017]仙人掌 解题报告

Description

如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。现在给定一张无自环无重边的无向连通图,求有多少种合法的加边方案,使得加边后原图是张仙人掌图。TT 组测试数据。

n5×105,m106\sum n\leq 5\times 10^5,\sum m\leq 10^6

Solution

阅读全文 »